Thứ tự từ điển

Trong các bộ từ điển, các từ được liệt kê theo thứ tự được gọi là thứ tự từ điển. Cho hai từ dưới dạng xâu của các ký tự

x = x 1 x 2 . . . x m {\displaystyle x=x_{1}x_{2}...x_{m}} y = y 1 y 2 . . . y n {\displaystyle y=y_{1}y_{2}...y_{n}}

Từ x được gọi là đứng trước từ y theo thứ tự từ điển nếu tồn tại chỉ số i, 1 ≤ i ≤ m i n { m , n } {\displaystyle 1\leq i\leq min\{m,\,n\}} sao cho

∀ j ≤ i : x j = y j {\displaystyle \forall j\leq i\,:\,x_{j}=y_{j}} x j + 1 {\displaystyle x_{j+1}} đứng trước y j + 1 {\displaystyle y_{j+1}}

Chú ý: Nếu j>m thì ta coi x j {\displaystyle x_{j}} là ký tự rỗng, tương tự nếu j>n thì coi y j {\displaystyle y_{j}} là ký tự rỗng, ký tự rỗng đứng trước mọi ký tự khác.

Liệt kê các hoán vị của tập n phần tử

Việc liệt kê toàn bộ các hoán vị của tập X = { x 1 , x 2 , . . . , x m } {\displaystyle X=\{x_{1},x_{2},...,x_{m}\}} được quy về việc liệt kê tất cả n! hoán vị của tập chỉ số { 1 , 2 , . . . , n } {\displaystyle \{1,2,...,n\}} . Ta sẽ liệt kê các hoán vị của n số tự nhiên { 1 , 2 , . . . , n } {\displaystyle \{1,2,...,n\}} theo thứ tự từ điển. Nhận xét rằng, khi xếp theo thứ tự từ điển, hoán vị đứng trước tiên sẽ là hoán vị ( 1 , 2 , 3 , . . . , n − 1 , n ) {\displaystyle (1,2,3,...,n-1,n)} , hoán vị đứng cuối cùng sẽ là hoán vị ( n , n − 1 , . . . , 2 , 1 ) {\displaystyle (n,n-1,...,2,1)} .Ví dụ với n=5, hoán vị đứng đầu là (1,2,3,4,5), đứng cuối là (5,4,3,2,1). Trong hoán vị đầu tiên mỗi số đều nhỏ hơn số đứng ngay sau nó, trong hoán vị cuối cùng thì ngược lại. Vậy kế tiếp sau hoán vị đầu tiên là hoán vị nào?

Hoán vị kế tiếp của một hoán vị (theo thứ tự từ điển)

Giả sử có hoán vị

x = ( x 1 , x 2 , . . . , x n − 1 , x n ) {\displaystyle x=(x_{1},x_{2},...,x_{n-1},x_{n})} của n số 1 , 2 , . . . , n {\displaystyle 1,2,...,n} .

• Thuật toán sinh hoán vị kế tiếp
  1. Tìm từ bên phải sang chỉ số i {\displaystyle i} sao cho x i − 1 < x i {\displaystyle x_{i-1}<x_{i}} .
  2. Nếu không tìm thấy thì trả lời x là hoán vị cuối cùng, không có hoán vị kế tiếp.
  3. Nếu có i như vậy:
     • sắp xếp các giá trị x i , . . . , x n {\displaystyle x_{i},...,x_{n}} theo thứ tự tăng dần.
     • đổi chỗ x i − 1 {\displaystyle x_{i-1}} cho phần tử lớn hơn x i − 1 {\displaystyle x_{i-1}} gần nhất trong các giá trị x i , . . . , x n {\displaystyle x_{i},...,x_{n}}

Ví dụ: với n=5

• kế tiếp của hoán vị ( 1 , 2 , 3 , 4 , 5 ) {\displaystyle (1,2,3,4,5)} là hoán vị ( 1 , 2 , 3 , 5 , 4 {\displaystyle (1,2,3,5,4} )
• kế tiếp của hoán vị ( 1 , 2 , 3 , 5 , 4 ) {\displaystyle (1,2,3,5,4)} là hoán vị ( 1 , 2 , 4 , 3 , 5 ) {\displaystyle (1,2,4,3,5)}
• kế tiếp của hoán vị ( 1 , 2 , 4 , 3 , 5 ) {\displaystyle (1,2,4,3,5)} là hoán vị ( 1 , 2 , 4 , 5 , 3 ) {\displaystyle (1,2,4,5,3)}

...

• kế tiếp của hoán vị ( 5 , 4 , 3 , 1 , 2 ) {\displaystyle (5,4,3,1,2)} là hoán vị ( 5 , 4 , 3 , 2 , 1 ) {\displaystyle (5,4,3,2,1)}

Thuật toán liệt kê tất cả các hoán vị của n số 1,2,...,n

1. Khởi tạo: x = ( 1 , 2 , . . . , n ) {\displaystyle x=(1,2,...,n)}
2. Tìm x' là hoán vị kế tiếp của x
3. Nếu không tìm được thì dừng.
4. Nếu thấy, thay x bằng x' quay lại 2.

Ví dụ: Liệt kê 24 hoán vị của 1,2,3,4 theo thứ tự từ điển

1234	1243	1324	1342	1423	1432
2134	2143	2314	2341	2413	2431
3124	3142	3214	3241	3412	3421
4123	4132	4213	4231	4312	4321

Liệt kê các tổ hợp chập k của tập n phần tử 1,2,3,4,5,6